模拟赛题解/2025.10.10 模拟赛

T1-我来，我见，我征服（cerydra）

题面

「凯撒」刻律德菈新发明了『征服棋』，这与国际象棋完全不同。

棋子，表示棋盘上的领土，都是长宽均为整数，且长宽比为 $2:1$ 的长方形。棋子数量充足，你可以认为每种大小的棋子都有 $10^{3960}$ 个。

第一次落子可以选择一枚任意大小的棋子，表示初始的领土；接下来每次落子都是 领土扩张。落子需要满足如下条件：

• 不能与之前的棋子重叠；
• 必须有一条边与之前的领土相邻；
• 落子后，领土必须仍为矩形，但长宽比可以不是 $2:1$。

「凯撒」刻律德菈最忠诚的剑旗，海瑟音问你：至少和至多分别要落多少棋子，领土形状才会成为 $n\times m$。 数据保证存在至少一种落子方式，使得领土形状都为 $n\times m$。

$1\leq n,m\leq 2\times 10^8$。

题解

我们先考虑不带任何优化的搜索且 $n≤m$：

• 对于 $2n=m$ 我们直接全删掉。
• 对于 $n$ 是偶数，我们显而易见可以删掉 $n\times \frac n2$ 的一个矩形。
• 对于 $2n<m$ 可以删掉一个 $n\times 2n$ 的一个矩形。
• 对于 $2n>m$ 可以删掉一个 $\frac m2\times m$ 的一个矩形。

然后我们考虑记忆化搜索，再考虑优化：

• 我们发现对于 $4n<m$ 时，我们设 $t=⌊\frac{m−1}{2n}⌋$ 可以一次性删除 $t$ 个 $n\times 2n$ 的矩形，将 $m$ 减小到 $m−2nt$。

T2-让告别，更美一些（castorice）

题面

安眠地的花丛中，有 $n$ 朵盛开的安提灵，第 $i$ 朵安提灵的高度是 $a_i$。

遐蝶已经将安提灵的高度修剪得互不相同，换而言之，$a$ 是一个长为 $n$ 的排列。

她将进行若干次操作以把数列 $a$ 变成目标数列 $b$。一次操作为选择 $1\leq l<r\leq n$，交换 $a_l,a_{l+1},a_{l+2},\cdots,a_r$ 中的最大值和最小值。例如，如果 $a$ 为 $[1,3,5,6,4,2]$，操作 $[2,5]$ 会使得 $a$ 变成 $[1,3,5,2,4,6]$。

遐蝶邀请你一起修剪花丛，你需要找出一种将数列 $a$ 变成数列 $b$ 的操作序列。

如果有多种可能的操作序列，你可以输出任意一种。

你需要保证操作序列长度不超过 $3\times 10^5$。

$1\leq T\leq 10,1\leq n\leq 4096,1\leq a_i\leq n$。

题解

注意到操作可逆，结合特殊性质 B 的提示想到可以将 $a,b$ 分别排序，再翻转操作序列。

考虑分治进行排序，合并两个有序的序列时：

• 如果它们值域上不相交，先将它们分别翻转，变成下降序列，然后翻转回来。需要使用 $O(n)$ 次操作。
• 否则对值域分治，如下图选择中位数将两个序列分开，对中间部分应用上述方法排序，得到两个子问题，递归即可。

时间复杂度类似 CDQ 分治，$O(n\log^2n)$ 可以通过。

T3-因你而在的故事（cyrene）

题面

昔涟给你讲了一个不同以往的浪漫故事：很久很久以前，有一个整数 $0\leq x\leq n$ 和守护这个数的昔涟（迷迷形态）。

你可以询问迷迷一个整数 $1\leq a\leq n$，如果 $a>x$，迷迷会回答“$\text{Me}\!\!\nearrow$”；反之，回答“$\text{Me}\!\!\searrow$”。

为了猜出 $x$，你想到了以下策略：先创建一个长为 $n$ 的排列 $p_1,p_2,p_3,\cdots,p_n$，然后按 $p_1$ 到 $p_n$ 的顺序依次猜数。

你会跳过不必要的猜测：如果你已经猜过 $a_1$，迷迷回答“$\text{Me}\!\!\nearrow$”而你现在要猜 $a_2>a_1$，则你跳过这次猜测；对称地，如果你已经猜过 $a_1$，迷迷回答“$\text{Me}\!\!\searrow$”而你现在要猜 $a_2<a_1$，则你也跳过这次猜测。可以说明，对于任意一个排列，该策略都能够猜出 $x$。

你想统计对于所有排列 $p$，你能让迷迷在连续两次询问中，发出的声音拼接后为“\text{Me}\!\!\nearrow$$\text{Me}\!\!\searrow”的次数的总和。

昔涟当然发现了你在占她便宜，她也发现答案可能很大，所以抓住你的手在题目描 述最后写下：答案对 $10^9+7$ 取模。

$1\leq T\leq 10^6,1\leq n\leq 10^7,0\leq x\leq n$。

题解

$x=0$ 或 $x=n$ 时答案为 $0$。

当 $0<x<n$ 时，记 $y=n-x,H_n=1+\frac12+\cdots+\frac1n$，结论：

$$E=\frac12\left(H_x+H_y-H_n+\frac yn\right)$$

规定 $H_0=0$，则 $x=n$ 时上式正确。

只需要归纳证明：$x$ 不变，$y$ 变成 $y+1$，即向原排列插入 $x+y+1$（回答“$\text{Me}\!\!\nearrow$”）时，期望的变化量

$$\begin{align} \Delta E &=\frac12\left(H_x+H_{y+1}-H_{n+1}+\frac {y+1}{n+1}\right)-\frac12\left(H_x+H_y-H_n+\frac yn\right)\\ &=\frac12\left(\frac1{y+1}-\frac1{n+1}+\frac {y+1}{n+1}-\frac yn\right)\\ &=\frac12\left(\frac1{y+1}+\frac {y}{n+1}-\frac yn\right) \end{align}$$

如果 $x+y+1$ 插入在此前第一个回答“$\text{Me}\!\!\nearrow$”的数之后，它会被忽略。所有未被忽略的回答“$\text{Me}\!\!\nearrow$”的数将排列分为 $y=1$ 段，因此此前第一个回答“$\text{Me}\!\!\nearrow$”的数之前的数的个数的期望为 $\frac{n-y}{y+1}=\frac x{y+1}$。

• 只要 $x+y+1$ 插入到下标在 $[1,\frac x{y+1}]$ 中的值最大的数之前就会与一个不被忽略的“$\text{Me}\!\!\searrow$”拼出一个 贡献，所以 $x+y+1$ 产生贡献的期望为 $\frac1{n+1}\cdot\frac12(\frac x{y+1}+1)=\frac1{2(y+1)}$；
• 上述期望需要减掉排列的第一个数对应的回答是“$\text{Me}\!\!\nearrow$”，即上述最大值不存在时多算的期望 $\frac12\cdot\frac yn$；
• 两项加起来与需要证明的值相等，于是证明该结论正确。

该式可以 $O(n)$ 预处理，$O(1)$ 计算。

T4-哀丽秘榭（phainon）

题面

哀丽秘榭有 $n$ 块沿水渠分布的麦田，你可以将麦田视为一棵无根树。

经过多年的积累，哀丽秘榭培育出了 $k$ 种优质小麦品种，第 $i$ 块麦田种植第 $a_i$ 种小麦，每一种小麦都有至少一块田在种植。

白厄从神悟树庭带来了每种小麦对应的肥料，他需要对于每种小麦，指定恰好一块种植了该种小麦的麦田，将肥料堆放在这里。记第 $i$ 种小麦堆放的麦田编号为 $b_i$。

为了不在施肥时出错，白厄希望对于每块麦田 $x$，满足 $dist(x,b_{a_x} )<\max_{i\not=a_x} dist(x,bi)$，其中 $dist(u,v)$ 表示麦田 $u$ 和麦田 $v$ 之间水渠的条数。换而言之，麦田到其所属集合中有小孩的麦田的树上距离必须小于到其它任何集合中有小孩的麦田的树上距离。

白厄找到你，请你构造一个合法的 $b$，或者说明无解。如果你能正确判断是否有解但有解时你不会构造 $b$，你也可以得到部分分数。

如果有多种可能的 $b$，你可以输出任意一种。

子任务的得分为其包含的各测试点的得分的最小值。对于单个测试点：

• 如果你不能正确判断是否有解，或者输出格式错误，获得 $0\%$ 的分数；
• 如果能正确判断是否有解，但是有解时构造的 $b$ 不合法，获得 $40\%$ 的分数；
• 如果能正确判断是否有解，并且有解时构造的 $b$ 合法，获得 $100\%$ 的分数；

$1\leq n\leq 2\times 10^5,1\leq a_i\leq k\leq n$。

题解

一组解 $b$ 是合法的，当且仅当：

• $a_i$ 相同的点连通；
• 将 $a_i$ 相同的点视为一个连通块，相邻两个连通块的 $b$ 到连接这两个连通块的边的距离相等。

先判掉 $a_i$ 相同的点不连通的情况。

设 $ok_u$ 表示处理 $u$ 所在的连通块的子树后，$u$ 能否堆放肥料。连通块 $x$ 的限制为：

• 设与其相邻的连通块 $y$ 中 $ok_u=true$ 的节点 $u$ 到连通块 $x,y$ 边界的距离为 $d$，那么 $b_x$ 到 $x,y$ 边界的距离也为 $d$；
• $b_x$ 满足来自 $y$ 的所有 $u$ 给出的限制中的任意一个即可。

这可以转化为设 $x,y$ 边界的边偏向 $x$ 一侧的点为 $p$，连通块 $x$ 中到 $p$ 的距离在一个集合（这个集合由连通块 $y$ 中的点 $u$ 给出）中的点全部加一，最终被加的次数等于与 $x$ 相邻的连通块数的点令 $ok=true$，否则 $ok=false$。

使用点分治完成上述处理即可判定是否有解，构造时按 $ok$ 数组依次推导即可，时间复杂度 $O(n\log n)$。